import java.util.Scanner;

public class day230416 {
    // 星际密码
    private static void fib(int[] fib) {
        fib[0] = 1;
        fib[1] = 2;
        for (int i = 2; i < fib.length; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
            fib[i] %= 10000; // 只要四位
        }
    }
    public static void main(String[] args) {
        // 存放 斐波那契数
        int[] fib = new int[10000];
        fib(fib);
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            for (int i = 0; i < n; i++) {
                // 不够四位,前面补0
                System.out.printf("%04d", fib[sc.nextInt() - 1]);
            }
            System.out.println();
        }
    }

    // 数根
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            // 数据范围 [1, 10^1000]
            // int, long 都放不下
            // 用String
            String s = sc.next();
            while (s.length() > 1) {
                int tmp = 0;
                for (char c : s.toCharArray()) {
                    tmp += c - 48;
                }
                s = String.valueOf(tmp);
            }
            System.out.println(s);
        }
    }

    public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            // 范围是 [1, 10^1000]
            // int, long 都放不下
            // 用 String
            String s = sc.next();
            // 先把S的所有数字相加
            // int 就够用了
            int n = 0;
            for (int i = 0; i < s.length(); i++) {
                n += (int)s.charAt(i) - 48;
            }
            while (n >= 10) {
                int tmp = n;
                n = 0;
                while (tmp != 0) {
                    n += tmp % 10;
                    tmp /= 10;
                }
            }
            System.out.println(n);
        }
    }
}
